# coding: utf-8
"""
@author: oldman
@file: 104_kth_largest_number.py
@time: 2021-08-02
""" 

"""
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

 

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
 

提示：

1 <= k <= nums.length <= 104
-104 <= nums[i] <= 104

"""


def kth_largets_nums(nums:list[int], k:int):
    """
    第K大的数
    :param k:
    :param nums:
    :return:
    """

    size = len(nums)
    target = size - k
    left = 0
    right = size -1

    while True:
        index = partition(nums, left, right)

        if index == target:
            return nums[index]
        elif index < target:
            left = index + 1
        else:
            right = index -1


def partition(nums, left, right):
    pivot = nums[left]
    j = left

    for i in range(left+1, right+1):
        if nums[i]< pivot:
            j += 1
            nums[i], nums[j] = nums[j], nums[i]

    nums[left], nums[j] = nums[j], nums[left]

    return j